package lc20240702;

import java.util.List;

/**
  * @description 求三角形节点路径和
  * @author 不知名帅哥
  * @date 2024/7/2 9:17
  * @version 1.0
*/
public class FindSumTriangle {
    public static void main(String[] args) {

    }
    //为什么从底向上计算
//    避免重复计算：每个节点只计算一次，利用了下一行已经计算好的结果。
//    简化实现：代码逻辑简单直接。
//    空间优化：在原地更新数据结构，节省空间。
    public int minimumTotal(List<List<Integer>> triangle){
        // 获取三角形的行数
        int n = triangle.size();

        // 从最后一行开始，逐层向上计算最小路径和
        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j < triangle.get(i).size(); j++) {
                // 更新当前节点的值为当前节点值加上下一行相邻节点中的较小值
                int minSum = Math.min(triangle.get(i + 1).get(j), triangle.get(i + 1).get(j + 1));
                triangle.get(i).set(j, triangle.get(i).get(j) + minSum);
            }
        }

        // 最后返回顶点的值，即为最小路径和
        return triangle.get(0).get(0);
    }
}
